|
|
Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (advisor) ; Bárány, Imre (referee) ; Valtr, Pavel (referee)
of doctoral thesis Problems in discrete geometry Zuzana Patáková This thesis studies three different questions from discrete geometry. A common theme for these problems is that their solution is based on algebraic methods. First part is devoted to the polynomial partitioning method, which par- titions a given finite point set using the zero set of a suitable polynomial. However, there is a natural limitation of this method, namely, what should be done with the points lying in the zero set? Here we present a general version dealing with the situation and as an application, we provide a new algorithm for the semialgebraic range searching problem. In the second part we study Ramsey functions of semialgebraic predi- cates. Conlon, Fox, Pach, Sudakov, and Suk constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function. We reduce the dimension of the ambient space in their construction and as a consequence, we provide a new geometric Ramsey-type theorem with a large Ramsey function. Last part is devoted to reptile simplices. A simplex S is k-reptile if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. We show that four-dimensional k-reptile simplices can exist only for k = m2 , where m ≥ 1...
|
|
|
Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (advisor) ; Bárány, Imre (referee) ; Valtr, Pavel (referee)
of doctoral thesis Problems in discrete geometry Zuzana Patáková This thesis studies three different questions from discrete geometry. A common theme for these problems is that their solution is based on algebraic methods. First part is devoted to the polynomial partitioning method, which par- titions a given finite point set using the zero set of a suitable polynomial. However, there is a natural limitation of this method, namely, what should be done with the points lying in the zero set? Here we present a general version dealing with the situation and as an application, we provide a new algorithm for the semialgebraic range searching problem. In the second part we study Ramsey functions of semialgebraic predi- cates. Conlon, Fox, Pach, Sudakov, and Suk constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function. We reduce the dimension of the ambient space in their construction and as a consequence, we provide a new geometric Ramsey-type theorem with a large Ramsey function. Last part is devoted to reptile simplices. A simplex S is k-reptile if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. We show that four-dimensional k-reptile simplices can exist only for k = m2 , where m ≥ 1...
|
guest ::
